package com.hxm.demo.sort;

import java.util.Arrays;

/**
 * @author huangxiaoming
 * @date 2022/6/22
 **/
public class QuickSort {
    /**
     * 快排
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] numbers = new int[]{13, 4, 34, 17, 2, 9};
        sort(numbers, 0, numbers.length - 1);
        System.out.println(Arrays.asList(numbers));

    }

    public static void sort(int[] numbers, int left, int right) {
        if (left >= right) {
            return;
        }
        int key = numbers[left];
        int i = left;
        int j = right;

        int emptyIndex = left;
        while (i < j) {
            //从右往左比较
            while (i < j && numbers[j] >= key) {
                j--;
            }
            if (i < j) {
                numbers[emptyIndex] = numbers[j];
                emptyIndex = j;
            }

            //从左往右比较
            while (i < j && numbers[i] <= key) {
                i++;
            }
            if (i < j) {
                numbers[emptyIndex] = numbers[i];
                emptyIndex = i;
            }
        }

        numbers[emptyIndex] = key;
        //左分割
        sort(numbers, left, i - 1);
        //右分割
        sort(numbers, i + 1, right);
    }
}
